#include <iostream>

using namespace std;

// 双重for循环
int strStr(string haystack, string needle) {
    for (int i{}, len1 = haystack.size(); i < len1; i++) {
        for (int j{}, len2 = needle.size(); j < len2; j++) {
            if (haystack[i + j] != needle[j]) {
                break;
            } else if (j == len2 - 1) {
                return i;
            }
        }
    }

    return -1;
}



void printNext(int* next, int len) {
    cout << "the next is: \n";
    for (int i{}; i < len; i++) {
        cout << next[i] << " ";
    }
    cout << "\n";
}

// 求next数组，此next数组对应在失配时下标所要回退的位置
// 即 PMT数组右移一位
void getNext(int* next, const string& p) {
    // next[0] = -1;
    // int i {}, j { -1 };
    // while (i < p.size()) {
    //     if (j == -1 || p[i] == p[j]) {
    //         i++;
    //         j++;
    //         // 注意这里最后一位容易越界
    //         if (i < p.size()) next[i] = j;
    //     } else {
    //         j = next[j];
    //     }
    // }

    // 这里求的是 PMT数组，没有进行任何修改 就是所谓的前缀表
    next[0] = 0;
    int j {};
    // i从1开始，
    for (int i = 1; i < p.size(); i++) {
        // 前后缀不同
        while (j > 0 && p[i] != p[j]) {
            j = next[j - 1]; // 向前回退
        }
        // 找到相同前后缀
        if (p[i] == p[j]) {
            j++;
        }
        next[i] = j; // 将j（前缀长度）赋值给next[i]
    }
}
// KMP算法
int strStr2(string haystack, string needle) {
    // 排除了 needle模式串为空串的情况
    int next[needle.size()];
    getNext(next, needle);

    printNext(next, needle.size());

    int j {}; // next 数组起始位置值为0
    for (int i = 0; i < haystack.size(); i++) {
        // 不匹配
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1]; // 寻找之前匹配位置
        }
        // 匹配
        if (haystack[i] == needle[j]) {
            j++; // j和i同时向后移动，i在for循环移动
        }
        if (j == needle.size()) {
            return i - needle.size() + 1;
        }
    }
    return -1;
}

int main() {
    string haystack { "hello" };
    string needle { "ll" };

    int result = strStr2(haystack, needle);

    cout << "The result is: " << result << "\n";
    
    return 0;
}